package io.gitee.wiqer.medium;

import io.gitee.wiqer.Interval;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * 描述
 * 给出一组区间，请合并所有重叠的区间。
 * 请保证合并后的区间按区间起点升序排列。
 *
 * 数据范围：区间组数 0 \le n \le 10000≤n≤1000，区间内 的值都满足 0 \le val \le 10000≤val≤1000
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 * 进阶：空间复杂度 O(val)O(val)，时间复杂度O(val)O(val)
 */
public class SolutionNC37_Merge {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        intervals.sort(new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        int j = 1;
        int i = 0;
        while (j < intervals.size()) {
            Interval before = intervals.get(i);
            Interval after = intervals.get(j);
            if (before.end >= after.start) {
                Interval tmp = new Interval(before.start, Math.max(before.end, after.end));
                intervals.remove(i); // 重点删除后，位置会往后移
                intervals.remove(i);
                intervals.add(i, tmp);  // 重点add, 不是set
            } else {
                i++;
                j++;
            }
        }
        return intervals;
    }
}
